import java.util.HashMap;
import java.util.Map;

public class Offer_39 {

    /**
     * 剑指 Offer 39. 数组中出现次数超过一半的数字
     * 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
     * <p>
     * <p>
     * <p>
     * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
     */
    public int majorityElement(int[] nums) {
        int length = nums.length;
        int harfNum;
        if (length % 2 == 0) {
            harfNum = length / 2;
        } else {
            harfNum = (length + 1) / 2;
        }
        Map<Integer, Integer> tempMap = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            if (!tempMap.containsKey(nums[i])) {
                tempMap.put(nums[i], 1);
            } else {
                tempMap.put(nums[i], tempMap.get(nums[i]) + 1);
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (tempMap.get(nums[i]) >= harfNum) {
                return nums[i];
            }
        }
        return -1;
    }
}
